In the related art, as a method for encoding an image, a color palette encoding method is known for representing the image with a palette holding one or more colors included in the image and an index indicating the color of each pixel of the image included in the palette. In the color palette encoding method, a method for efficiently encoding the palette or the index is important to improve efficiency of encoding the image.
As a technique to which such a color palette encoding method is applied, a technique is known for improving encoding efficiency by creating a palette from a pixel encoded earlier than a pixel as an encoding target. Another technique is known for improving encoding efficiency by acquiring appearance frequency of the color from an input image (or part thereof) in advance, and performing variable length encoding on the index based on the frequency to reduce a code amount of the index.